multiplicative spanner

Definition (multiplicative spanner)

(α,β)-spanner where $\beta = 0$. (i.e. an $(\alpha,0)$-spanner or $\alpha$-multiplicative spanner)

Theorem (Althöfer-Das-Dobkin-Joseph-Soares 1993)

For every $k \geq 1$, every $n$-node graph $G$ has a $(2k-1)$-multiplicative spanner $G' \subseteq G$ with $O(n^{1+1/k})$ edges.

Erdős girth conjecture

For every $k \geq 1$, there exists an $n$-node graph with $\Omega(n^{1+1/k})$ edges and girth at least $2k+2$. (Erdős girth conjecture) (unproven beyond small values of $k$)

References

1. https://people.csail.mit.edu/ghaffari/AA18/Notes/S2.pdf
2. I. Althöfer, G. Das, D. Dobkin, D. Joseph, and J. Soares, “On sparse spanners of weighted graphs,” Discrete Comput Geom, vol. 9, no. 1, pp. 81–100, Jan. 1993, doi: 10.1007/BF02189308.
3. P. Erdös and L. Moser, “An extremal problem in graph theory,” J. Aust. Math. Soc., vol. 11, no. 1, pp. 42–47, Feb. 1970, doi: 10.1017/S1446788700005954.